import java.util.Random;
class SortAnArray {

    /**
     * 方法：快速排序
     * 使用分治法，通过随机选取基准值将数组分为两部分，分别对左右部分递归排序
     * 
     * Args:
     *   nums: int[], 待排序的数组
     * 
     * Returns:
     *   int[]: 排序后的数组
     * 
     * Time: O(nlogn), 平均情况下每次划分将问题规模减半
     * Space: O(logn), 递归调用栈的深度
     */
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int l, int r){
        if (l >= r) {
            return;
        }
        int pivotIndex = new Random().nextInt(r - l + 1) + l;
        int pivot = nums[pivotIndex];
        swap(nums, l, pivotIndex);

        int i = l + 1;
        int j = r;
        while (true) {
            while (i <= r && nums[i] < pivot) {
                i++;
            }
            while (j >= l + 1 && nums[j] > pivot) {
                j--;
            }
            if (i > j) {
                break;
            }
            swap(nums, i, j);
            i++;
            j--;
        }
        swap(nums, l, j);
        quickSort(nums, l, j - 1);
        quickSort(nums, j + 1, r);

    }

    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}